package com.chapter5.string;

import java.util.Arrays;

/**
 * 
* @ClassName: LRS 
* @Description: longest repeated substring 最长的重复的子字符串 
* @author minjun
* @date 2015年3月20日 下午9:22:23 
*
 */
public class LRS {

	public static String lrs(String s){
		//求出suffix array
		int len=s.length();
		String[] suffix=new String[len];
		for(int i=0;i<len;i++){
			suffix[i]=s.substring(i);
		}
		
		//将suffix array排序
		Arrays.sort(suffix);
		
		//找到最长的重复的子字符串
		String lcp="";
		for(int i=0;i<len-1;i++){
			int length=lcp(suffix[i],suffix[i+1]);
			if(length>lcp.length()){
				lcp=suffix[i].substring(0, length);
			}
		}
		
		return lcp;
	}

	/**
	 * 
	* @Title: lcp 
	* @Description: 从起始位置找到两个字符串最长的相同子字符串 
	* @param @param a
	* @param @param b
	* @param @return    设定文件 
	* @return String    返回类型 
	* @throws
	 */
	private static int lcp(String a, String b) {
		int len=Math.min(a.length(), b.length());
		for(int i=0;i<len;i++){
			if(a.charAt(i)!=b.charAt(i)){
				return i;
			}
		}
		
		return len;
	}
}
